package org.ponly.lpf4j.util.graph;

import gnu.trove.TIntArrayList;
import gnu.trove.TObjectIntHashMap;
import org.ponly.lpf4j.util.Couple;
import org.ponly.lpf4j.util.IntStack;

import java.util.*;

/**
 * @author dsl, ven
 */
public class DFSTBuilder<Node> {
    private final Graph<Node> myGraph;
    private final TObjectIntHashMap<Node> myNodeToNNumber; // node -> node number in topological order [0..size). Independent nodes are in reversed loading order (loading order is the graph.getNodes() order)
    private final Node[] myInvN; // node number in topological order [0..size) -> node
    private Couple<Node> myBackEdge;

    private Comparator<Node> myComparator;
    private final TIntArrayList mySCCs = new TIntArrayList(); // strongly connected component sizes
    private final TObjectIntHashMap<Node> myNodeToTNumber = new TObjectIntHashMap<Node>(); // node -> number in scc topological order. Independent scc are in reversed loading order

    private final Node[] myInvT; // number in (enumerate all nodes scc by scc) order -> node
    private final Node[] myAllNodes;

    public DFSTBuilder(Graph<Node> graph) {
        myAllNodes = (Node[]) graph.getNodes().toArray();
        myGraph = graph;
        int size = graph.getNodes().size();
        myNodeToNNumber = new TObjectIntHashMap<Node>(size * 2, 0.5f);
        myInvN = (Node[]) new Object[size];
        myInvT = (Node[]) new Object[size];
        new Tarjan().build();
    }

    /**
     * Tarjan strong-connect-components search algorithm.
     * See e.g. <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm</a><br>
     * This implementation differs from the canonical one above by<br>
     * <ul>
     * <li>- being not recursive</li>
     * <li>- computing also topological order during the same single pass</li>
     * </ul>
     */
    private class Tarjan {
        private final int[] lowLink = new int[myInvN.length];
        private final int[] index = new int[myInvN.length];

        private final IntStack nodesOnStack = new IntStack();
        private final boolean[] isOnStack = new boolean[index.length];

        private class Frame {
            public Frame(int nodeI) {
                this.nodeI = nodeI;
                Iterator<Node> outNodes = myGraph.getOut(myAllNodes[nodeI]);
                TIntArrayList list = new TIntArrayList();

                while (outNodes.hasNext()) {
                    Node node = outNodes.next();
                    list.add(nodeIndex.get(node));
                }
                out = list.toNativeArray();
            }

            private final int nodeI;
            private final int[] out;
            private int nextUnexploredIndex;

            @Override
            public String toString() {
                final StringBuilder o = new StringBuilder();
                for (int id : out) {
                    o.append(myAllNodes[id]).append(", ");
                }
                return myAllNodes[nodeI] + " -> [" + o + "]";
            }
        }

        private final Stack<Frame> frames = new Stack<Frame>(); // recursion stack
        private final TObjectIntHashMap<Node> nodeIndex = new TObjectIntHashMap<Node>();
        private int dfsIndex;
        private int sccsSizeCombined;
        private final TIntArrayList topo = new TIntArrayList(index.length); // nodes in reverse topological order

        private void build() {
            Arrays.fill(index, -1);
            for (int i = 0; i < myAllNodes.length; i++) {
                Node node = myAllNodes[i];
                nodeIndex.put(node, i);
            }
            for (int i = 0; i < index.length; i++) {
                if (index[i] == -1) {
                    frames.push(new Frame(i));
                    List<List<Node>> sccs = new ArrayList<List<Node>>();

                    strongConnect(sccs);

                    for (List<Node> scc : sccs) {
                        int sccSize = scc.size();

                        mySCCs.add(sccSize);
                        int sccBase = index.length - sccsSizeCombined - sccSize;

                        // root node should be first in scc for some reason
                        Node rootNode = myAllNodes[i];
                        int rIndex = scc.indexOf(rootNode);
                        if (rIndex != -1) {
                            swapElements(scc, rIndex, 0);
                        }

                        for (int j = 0; j < scc.size(); j++) {
                            Node sccNode = scc.get(j);
                            int tIndex = sccBase + j;
                            myInvT[tIndex] = sccNode;
                            myNodeToTNumber.put(sccNode, tIndex);
                        }
                        sccsSizeCombined += sccSize;
                    }
                }
            }

            for (int i = 0; i < topo.size(); i++) {
                int nodeI = topo.get(i);
                Node node = myAllNodes[nodeI];

                myNodeToNNumber.put(node, index.length - 1 - i);
                myInvN[index.length - 1 - i] = node;
            }
            mySCCs.reverse(); // have to place sccs in topological order too
        }

        private void strongConnect(List<List<Node>> sccs) {
            int successor = -1;
            nextNode:
            while (!frames.isEmpty()) {
                Frame pair = frames.peek();
                int i = pair.nodeI;

                // we have returned to the node
                if (index[i] == -1) {
                    // actually we visit node first time, prepare
                    index[i] = dfsIndex;
                    lowLink[i] = dfsIndex;
                    dfsIndex++;
                    nodesOnStack.push(i);
                    isOnStack[i] = true;
                }
                if (indexOf(pair.out, successor) != -1) {
                    lowLink[i] = Math.min(lowLink[i], lowLink[successor]);
                }
                successor = i;

                // if unexplored children left, dfs there
                while (pair.nextUnexploredIndex < pair.out.length) {
                    int nextI = pair.out[pair.nextUnexploredIndex++];
                    if (index[nextI] == -1) {
                        frames.push(new Frame(nextI));
                        continue nextNode;
                    }
                    if (isOnStack[nextI]) {
                        lowLink[i] = Math.min(lowLink[i], index[nextI]);

                        if (myBackEdge == null) {
                            myBackEdge = Couple.of(myAllNodes[nextI], myAllNodes[i]);
                        }
                    }
                }
                frames.pop();
                topo.add(i);
                // we are really back, pop a scc
                if (lowLink[i] == index[i]) {
                    // found yer
                    List<Node> scc = new ArrayList<Node>();
                    int pushedI;
                    do {
                        pushedI = nodesOnStack.pop();
                        Node pushed = myAllNodes[pushedI];
                        isOnStack[pushedI] = false;
                        scc.add(pushed);
                    }
                    while (pushedI != i);
                    sccs.add(scc);
                }
            }
        }
    }


    public Comparator<Node> comparator() {
        if (myComparator == null) {
            final TObjectIntHashMap<Node> map = isAcyclic() ? myNodeToNNumber : myNodeToTNumber;
            myComparator = new Comparator<Node>() {
                @Override
                public int compare(Node t, Node t1) {
                    return map.get(t) - map.get(t1);
                }
            };
        }
        return myComparator;
    }

    public Couple<Node> getCircularDependency() {
        return myBackEdge;
    }

    public boolean isAcyclic() {
        return getCircularDependency() == null;
    }


    public Node getNodeByNNumber(final int n) {
        return myInvN[n];
    }


    public Node getNodeByTNumber(final int n) {
        return myInvT[n];
    }

    /**
     * @return the list containing the number of nodes in strongly connected components.
     * Respective nodes could be obtained via {@link #getNodeByTNumber(int)}.
     */

    public TIntArrayList getSCCs() {
        return mySCCs;
    }


    public List<Node> getSortedNodes() {
        List<Node> result = new ArrayList<Node>(myGraph.getNodes());
        Collections.sort(result, comparator());
        return result;
    }

    private static <E> void swapElements(List<E> list, int index1, int index2) {
        E e1 = list.get(index1);
        E e2 = list.get(index2);
        list.set(index1, e2);
        list.set(index2, e1);
    }

    public static int indexOf(int[] ints, int value) {
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] == value) return i;
        }
        return -1;
    }
}